/*
 * @lc app=leetcode.cn id=117 lang=javascript
 *
 * [117] 填充每个节点的下一个右侧节点指针 II
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
  if (!root) return null
    let lastPost = root
    while (lastPost) {
      let node = lastPost
      let next = node.next
      let nextPost = null
      // 下一个节点
      while (node) {
        if (!nextPost && (node.left || node.right)) {
          nextPost = node.left || node.right
        }
        // 有左节点和右节点时，把右节点连接到左节点
        if (node.left && node.right) {
          node.left.next = node.right
        }

        if (next) {
          // 如果当前节点没有子节点，那么跳过，处理后面节点
          if (!node.right && !node.left) {
            node = next
            next = next.next
          }
          // 如果next对应的节点没有子节点,跳过
          else if (!next.left && !next.right) {
            next = next.next
          } else {
            (node.right || node.left).next = 
            next.left || next.right;
            node = next
            next = next.next
          }
        } else {
          node = null
        }
      }
      lastPost = nextPost
    }
    return root
};
// @lc code=end

